0/1 Knapsack with Branch and Bound - Interactive Tutorial

👩‍💻 Alice's Knapsack Challenge

🎯 The Mission:

Help Alice maximize her profit by selecting items with the best value-to-weight ratio within the knapsack's weight capacity using Branch and Bound.

📋 Requirements:

Select items to maximize total value
Respect knapsack weight capacity W
Each item has weight and value
Output maximum value, rounded to two decimal places

Input/Output Specifications

Input: N (number of items), W (knapsack capacity), N weights, N values
Output: Maximum value (float, two decimal places)
Constraints: 1 ≤ N ≤ 100, 1 ≤ W ≤ 1000, 1 ≤ weight[i] ≤ 100, 1 ≤ value[i] ≤ 1000

Example 1: N=4, W=10, weights=[2,3,5,4], values=[40,50,100,60]

Items:

W:2, V:40

W:3, V:50

W:5, V:100

W:4, V:60

Output: 190.00

Example 2: N=4, W=10, weights=[2,3,4,1], values=[10,15,20,5]

Items:

W:2, V:10

W:3, V:15

W:4, V:20

W:1, V:5

Output: 50.00

⚡ Branch and Bound Explained

How Branch and Bound Works for Knapsack

Sort Items: Order items by value-to-weight ratio in descending order
Bound Function: Calculate upper bound for a node by adding current profit and maximum possible profit from remaining items
Explore Nodes: Use a queue to explore nodes (include/exclude item), pruning branches with bound ≤ current max profit
Track Maximum: Update max profit when a valid solution is found

Example Decision Tree (N=2, W=5, weights=[2,3], values=[40,50])

Root: Profit=0, Weight=0, Bound=90

Include Item 1 (W:2, V:40): Profit=40, Weight=2, Bound=90

Exclude Item 1: Profit=0, Weight=0, Bound=50

Output: 50.00 (select item 2)

Time Complexity

O(2^N)

Worst case, but pruning reduces nodes explored

Space Complexity

O(N)

For queue and recursion stack

Why Branch and Bound?

✅ Optimizes by pruning suboptimal branches
✅ Handles 0/1 item selection
✅ Useful for combinatorial optimization
❌ Can be exponential without effective pruning

🔍 Step-by-Step Branch and Bound Demo

Enter N and W (e.g., "4 10"):

Enter weights (space-separated):

Enter values (space-separated):

Click "Start Demo" to begin step-by-step visualization

Algorithm Progress:

1. Display input items

2. Sort by value/weight ratio

3. Explore decision tree

4. Display result

Current Items (Sorted):

Algorithm State:

Node ID	Level	Profit	Weight	Bound	Action

Decision Tree:

🎮 Practice Knapsack with Branch and Bound

Enter N and W (e.g., "4 10"):

Enter weights (space-separated):

Enter values (space-separated):

Enter inputs, then click "Compute Max Value"

Test Cases

Example 1: N=4, W=10, weights=[2,3,5,4], values=[40,50,100,60] → 190.00

Example 2: N=4, W=10, weights=[2,3,4,1], values=[10,15,20,5] → 50.00

📊 Algorithm Analysis

Branch and Bound Process

Sort Items: By value-to-weight ratio in descending order
Initialize: Start with root node (level=-1, profit=0, weight=0)
Explore Nodes: For each node, create branches for including/excluding the next item, compute bound, and prune if bound ≤ maxProfit
Output: Maximum profit, rounded to two decimal places

struct Item {
    int weight, value;
    double ratio;
};

struct Node {
    int level, profit, weight;
    double bound;
};

double bound(Node u, int n, int W, vector& items) {
    if (u.weight >= W) return 0;
    double profit_bound = u.profit;
    int j = u.level + 1;
    int totweight = u.weight;
    while (j < n && totweight + items[j].weight <= W) {
        totweight += items[j].weight;
        profit_bound += items[j].value;
        j++;
    }
    if (j < n) {
        profit_bound += (W - totweight) * items[j].ratio;
    }
    return profit_bound;
}

int main() {
    int N, W;
    cin >> N >> W;
    vector<int> weights(N), values(N);
    for (int i = 0; i < N; i++) cin >> weights[i];
    for (int i = 0; i < N; i++) cin >> values[i];

    vector items(N);
    for (int i = 0; i < N; i++) {
        items[i].weight = weights[i];
        items[i].value = values[i];
        items[i].ratio = (double)values[i] / weights[i];
    }

    sort(items.begin(), items.end(), [](Item a, Item b) {
        return a.ratio > b.ratio;
    });

    queue Q;
    Node u, v;
    u.level = -1; u.profit = 0; u.weight = 0;
    u.bound = bound(u, N, W, items);
    double maxProfit = 0.0;

    Q.push(u);
    while (!Q.empty()) {
        u = Q.front(); Q.pop();
        if (u.level == N - 1) continue;

        v.level = u.level + 1;
        v.weight = u.weight + items[v.level].weight;
        v.profit = u.profit + items[v.level].value;
        if (v.weight <= W && v.profit > maxProfit) maxProfit = v.profit;
        v.bound = bound(v, N, W, items);
        if (v.bound > maxProfit) Q.push(v);

        v.weight = u.weight;
        v.profit = u.profit;
        v.bound = bound(v, N, W, items);
        if (v.bound > maxProfit) Q.push(v);
    }

    cout << fixed << setprecision(2) << maxProfit;
    return 0;
}
            

🎒 0/1 Knapsack with Branch and Bound

👩‍💻 Alice's Knapsack Challenge

🎯 The Mission:

📋 Requirements:

Input/Output Specifications

Example 1: N=4, W=10, weights=[2,3,5,4], values=[40,50,100,60]

Example 2: N=4, W=10, weights=[2,3,4,1], values=[10,15,20,5]

⚡ Branch and Bound Explained

How Branch and Bound Works for Knapsack

Example Decision Tree (N=2, W=5, weights=[2,3], values=[40,50])

Time Complexity

O(2^N)

Space Complexity

O(N)

Why Branch and Bound?

🔍 Step-by-Step Branch and Bound Demo

Algorithm Progress:

Current Items (Sorted):

Algorithm State:

Decision Tree:

🎮 Practice Knapsack with Branch and Bound

Test Cases

📊 Algorithm Analysis

Branch and Bound Process

Time Complexity

O(2^N)

Space Complexity

O(N)

Key Points